#include <limits.h>  // INT_MIN,INT_MAX
#include <math.h>    // abs,pow

#include <algorithm>      // sort
#include <iostream>       // cout,cin
#include <numeric>        // accumulate
#include <string>         // string
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <vector>         // vector

using namespace std;

// 链表结点的数据结构
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

// 多级双向链表结点及
class Node {
   public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};

// 如果x是2的幂则返回True，否则返回False
bool IsPowerOf2(int x) { return (x & (x - 1)) == 0; }

class Solution {
   public:
    Node* flatten(Node* head) {
        if (head) {
            head = dfs(head);
            head->prev = nullptr;
            return head;
        } else {
            return head;
        }
    }

   private:
    // 扁平化链表：第一个结点的prev指向最后一个结点
    Node* dfs(Node* head) {
        Node *curr = head, *last = nullptr;
        while (curr) {
            Node* next = curr->next;  // 当前层级下一个结点
            if (curr->child) {
                Node* child_head = dfs(curr->child);  // 子层级第一个结点
                Node* child_tail = child_head->prev;  // 子层级最后一个结点
                curr->child = nullptr;

                curr->next = child_head;
                child_head->prev = curr;

                if (next) {
                    next->prev = child_tail;
                    child_tail->next = next;
                    last = child_tail;
                    curr = next;
                } else {
                    last = child_tail;
                    curr = nullptr;
                }
            } else {
                last = curr;
                curr = curr->next;
            }
        }
        head->prev = last;
        return head;
    }
};

int main() {
    Solution solution;
    return 0;
}